Ütemező programtervezési minta

A számítógép-programozásban, az Ütemező (angolul scheduler) minta egy programtervezési minta. Ez egy párhuzamossági minta, melyet akkor használunk, amikor a szálak egyszálú kódokat hajtanak végre, mint például egy fájlírási művelet. Szálakat, folyamatokat, adatfolyamokat kezel, amelyeket processzorokra, hálózati kapcsolatokra és kiegészítő kártyákra (grafikus kártya, memóriakártya) ütemez.

Az ütemező egy objektum, amely szekvenciálisan várakozik a szálakra. Ez mechanizmust biztosít egy ütemezési szabályrendszer implementálására, de független bármilyen más konkrét ütemezési szabálytól – A szabály egységbe van zárva a saját osztályába, és újrafelhasználható. Gyakran úgy van kialakítva, hogy lefoglalja az összes erőforrást. Az ütemező mintával olyan számítógép is működhet virtuálisan párhuzamosan, aminek csak egy processzora van.

Az olvas / ír záró (Lock) minta általában az ütemező minta által is megvalósítható, a tisztességes feltételek biztosítása érdekében. Az Ütemező minta jelentősen növeli a feldolgozási időt, és hívásához szinkronizált metódus szükséges. Az Ütemező minta nem teljesen ugyanaz, mint a Feladat-ütemező minta, melyet a valós-idejű (Real-Time) rendszereknél használunk.

Az ütemező alkalmazásának több célja lehet. Maximalizálhatja az időegység alatt elvégzett munkát, minimalizálhatja az átfutási időt (latency, egy feladat engedélyezése és befejezése között eltelt időtartam), minimalizálhatja a válaszidőt, maximalizálhatja a korrektséget. Ezek a célok gyakran ellentmondanak egymásnak, ezért az ütemezőnek a megfelelő egyensúlyt kell megvalósítania. A felhasználó és a rendszer igényeinek és céljainak megfelelően kell dönteni arról, hogy melyik cél a fontosabb.

Valós idejű környezetekben az ütemezőnek a határidők betartását is biztosítania kell. Ilyenek a robotok és az automata vezérlésű beágyazott rendszerek. Erre feltétlenül szükség van a rendszer stabilitásának érdekében. Az ütemező hálózaton keresztül is eloszthatja a feladatokat egy adminisztratív központból.

Időzítési algoritmusok

Az ütemezési algoritmusok a forrásokat olyan folyamatok között osztják szét, amelyek aszinkron módon igényelnek néhányat az erőforrások közül. Használják a routerekben a csomagok irányításához, operációs rendszerekben a folyamatok időmegosztására, lemezmeghajtókban író-olvasó ütemezésre, nyomtatókhoz, beágyazott rendszerekhez.

Az ütemezők fő célja az, hogy megelőzzék a kiéheztetést, és korrektséget biztosítsanak az erőforrások elosztásában. Az ütemező osztja el az erőforrásokat, ő dönt arról, hogy ha több folyamat igényli ugyanazokat az erőforrásokat, akkor melyik kapja meg.

Hálózati kommunikációban az ütemező az először be, először ki elvének alternatíváját jelenti.

Egyszerű de hatékony algoritmusok a round robin, a max-min fair sor, az arányos fair időzítés és az időegység alatt elvégzett feladatok maximalizálása. Ha a szolgáltatás minőségét is megkülönböztetik, és szembeállítják a legjobb erőfeszítésű kommunikációval, a súlyozott fair sor ajánlható.

A vezeték nélküli rádióhálózatban mint a HSDPA (High-Speed Downlink Packet Access) 3.5G sejtrendszerben a csatornafüggő ütemezés használható arra, hogy a csatorna állapotáról információhoz jussunk. Megfelelő esetben növelhetjük az időegység alatt elvégzett feladatok számát, és a rendszer spektrális hatékonyságot. Fejlettebb rendszerekben, mint az LTE, az ütemezés kombinálható a csatornafüggő csomagonkénti dinamikus csatornaallokációval, vagy az OFDMA multihordozók allokálásával vagy más frekvenciatartományi kiegyenlítésével, olyan komponensekkel, amiket a felhasználó a legjobban tud hasznosítani.

A munkakonzervatív ütemező arra törekszik, hogy a beütemezett folyamatoknak mindig legyen feladatuk. Az ütemező preemptív, ha megszakíthatja az éppen futó folyamatot, és helyette egy másikat indíthat el.

Először érkező először

Az először érkező először (ismert úgy is, mint FIFO vagy FCFS) egy egyszerű, sort használó ütemezési algoritmus. A szálkészlet programtervezési minta is ezen alapul. Az érkező folyamatokat az ütemező beteszi a várakozási sorba, ha pedig lehet, akkor elindítja a legrégibb feladatot.

• Mivel kontextusváltás csak akkor történik, amikor véget ér egy feladat, és a folyamatsor nem igényel átrendezést, az ütemezés kevés adminisztrációs költséggel jár.
• Az egyszerre végzett feladatok száma kevés lehet, mivel a hosszú folyamatok feltarthatják a rövideket. Erre példa az, hogy a teli kosarú vásárló megelőzi azt, aki csak egy cikket akar venni; ez utóbbi több időt veszít, mint amennyit az elöl álló nyer. Ez konvoj hatásként is ismert.
• Nincs kiéheztetés, mivel a folyamatok meghatározott idő után sorra kerülnek.
• A teljes végrehajtási idő, a várakozási és a válaszadási idő nagy lehet, függően a beérkező feladatok sorrendjétől.
• Nincs priorizálás, így ez a módszer nem alkalmas a határidők betartatására.

Legkorábbi határidő először

A legkorábbi határidő először (EDF) egy dinamikus ütemezési algoritmus, amit valós idejű operációs rendszereken használnak. A folyamatok határidejük alapján prioritási sorba kerülnek, Ütemezési esemény (feladat vége, feladat indítása) esetén az ütemező megkeresi a sorban azt a feladatot, aminek a legközelebbi a határideje. A következő alkalommal ennek kell elindulnia.

Legrövidebb hátralevő idejű először

Hasonló a legrövidebb feladat először (SJF) ütemezéshez. Az ütemező úgy rendezi a feladatokat, hogy az kerül előre, aminek a legrövidebb a becsült hátralevő ideje. Ez azt igényli, hogy ezt az időt meg lehessen becsülni.

• Ha a beérkező feladat becsült végrehajtási ideje rövidebb, mint az éppen futó feladat hátralevő ideje, akkor az ütemező megszakítja, és a rövid feladatot indítja el. A kontextusváltás és a sor rendezgetése miatt az adminisztrációs költség nagy.
• A legtöbb esetben biztosítja, hogy időegység alatt minél több feladat hajtódjon végre.
• A várakozási és a válaszadási idő együtt nő a folyamat számítási igényével. Mivel a teljes időbe beleszámít a várakozás is, ez megérződik a hosszabb folyamatoknál. Azonban az átlagos várakozási idő rövidebb, mint a FIFO esetén, hiszen nem kell a leghosszabb folyamat befejezésére várni.
• Magukat a határidőket nem figyeli az ütemező. A programozóknak kell arra ügyelniük, hogy a feladatoknak olyan határidejük legyen, amennyi idő alatt éppen végre tudjanak hajtódni. Az ennél hosszabb határidőket a rendszer bünteti.
• A módszer használatához különböző prioritású folyamatokra van szükség. Például a rendszerfeladatoknak lehet nagyobb a prioritása.
• 2014-ben ezt a módszert ritkán használták.

Rögzített prioritású preemptív ütemezés

A folyamatok ütemezése prioritásukon alapul. Ha nincs prioritás, akkor az FPPS a FIFO algoritmusba megy át. A sorban a feladatokat az ütemező prioritásuk szerint rendezi. Az alacsony prioritású folyamatokat megszakítja a beérkező magas prioritású feladat.

• Az adminisztrációs költség alacsony.
• Ha a kiosztható prioritások korlátosak, akkor minden prioritáshoz külön FIFO tartozik. Az alacsonyabb prioritású sorokból akkor jöhet feladat, ha a magasabb prioritású sorok üresek.
• A FIFO-val szemben nincs időegység alatt elvégzett feladatok számában előnye.
• A várakozási és a válaszadási idő függ a feladat prioritásától. A nagyobb prioritásúaké kisebb.
• A prioritás meghatározza, hogy a folyamat be tudja-e tartani a feladat határidejét.
• Kiéheztetés előfordulhat, ha sorra jönnek a nagy prioritású feladatok.

Round-robin ütemezés

Az időzítő a CPU-időt szeletekre osztja. A folyamatokat ciklikusan járja végig. Ha egy folyamat véget ért, akkor törli a ciklusból, és az időszeletet a következő folyamat kaphatja meg.

• Az adminisztrációval töltött idő nagy, különösen, ha az időszeletek rövidek.
• Az időegység alatt végrehajtott feladatok száma az FCFS/ FIFO és az SJF/SRTF közötti. A rövid folyamatok hamarabb véget érnek, mint a FIFO esetén, és a hosszú folyamatok előbb végeznek, mint SJF esetén.
• Az átlagos várakozási idő a folyamatok számától függ, hosszuktól nem; az átlagos válaszadási idő kicsi.
• Nem lehet prioritást használni. Ezért kiéheztetés sincs. Az idő allokálása az érkezési sorrendtől függ.
• A várakozási idők hosszúak, ezért határidőket nem lehet betartani.
• Ha az időszelet hosszú, illetve sok a rövid feladat, akkor FCFS /FIFO, ha rövid, akkor SJF/SRTF lesz.

Többszintű sor ütemezés

A feladatokat és a folyamatokat csoportokra osztják, például előtérben és háttérben futó folyamatok. A különböző csoportokra különböző ütemezési módszereket használnak, mivel mások az elvárások a válaszadási időt illetően. Megosztott memória kezeléséhez hasznos.

Kézi ütemezés

A kézi ütemezés gyakran alkalmazott módszer, amit például idő-multiplexeléssel érnek el. Néha a kernelt három részre osztják: Kézi ütemezés, preemptív és megszakítási szint. Az ütemezőt gyakran kereskedelmi könyvtár nyújtja.

• Nincs kiéheztetés
• Megjósolhatóság: a határidők betarthatók.
• Nincs adminisztrációs költség.
• Nem mindig optimális.
• A hatékonyság az optimalizációtól függ.

Az ütemező kiválasztása

Ha ütemezőt kell választania, akkor a programozónak mérlegelnie kell, hogy milyen tulajdonságokat tart fontosnak, és melyekről tud lemondani. Sok operációs rendszerben több ütemezési algoritmus keverékét használja.

Például a Windows NT/XP/Vista többszintű visszacsatolásos sort használ, ami kombinálja a következőket: rögzített prioritású preemptív ütemezés, round robin, és a FIFO. Ebben a rendszerben a folyamatok prioritása változhat, attól függően, hogy mióta vár, vagy hogy mit végzett eddig. Minden szintet külön sor reprezentál, a magasabb prioritású szálaknál round robin, és az alacsonyabb prioritásúaknál FIFO. Ebben a rendszerben a válaszadási idő a legtöbb folyamatnál alacsony, és a rövid, de kritikus fontosságú rendszerfeladatok hamar véget érhetnek. Azonban a magas prioritású, de hosszú feladatok várakozási ideje hosszú, kiéheztetés előfordulhat.

Példa kód (C#)

using System;

namespace Digital_Patterns.Concurrency.Sheduler
{
    class Printer
    {
        private static Int32 mID = 0;

        private Scheduler _scheduler = new Scheduler();

        public void Print(JournalEntry journalEntry)
        {
            Int32 id = ++mID;
            try
            {
                Console.WriteLine(String.Format(@"{0}: enter scheduler", id));
                // вызов не выполнится до тех пор, пока объект Scheduler не решит,
                // что подошла очередь распечатать этот объект JournalEntry
                _scheduler.Enter(journalEntry);
                Console.WriteLine(String.Format(@"{0}: start printing", id));
                try
                {
                    //TODO Something
                    journalEntry.Do(id);
                }
                finally
                {
                    // вызов метода Done говорит Scheduler о том, что объект JournalEntry
                    // распечатан, и может подойти очередь вывода на печать другого объекта
                    // JournalEntry
                    _scheduler.Done();
                    Console.WriteLine(String.Format(@"{0}: done scheduler", id));
                }
            }
            catch (Exception) {}
        }
    }
}

using System;
using System.Collections.Generic;
using System.Threading;

namespace Digital_Patterns.Concurrency.Sheduler
{
    /// <summary>
    /// Экземпляры классов в этой роли управляют обработкой объектов Request <see cref="JournalEntry"/>,
    /// выполняемой объектом Processor <see cref="Printer"/>. Чтобы быть независимыми от типов
    /// запросов, класс <see cref="Scheduler"/> не должен ничего знать об управляемом им классе Request.
    /// Вместо этого он осуществляет доступ к объектам Request через реализуемый ими интерфейс <see cref="ISchedulerOrdering"/>
    /// </summary>
    class Scheduler
    {
        /// <summary>
        /// Объект синхронизации потоков
        /// </summary>
        private AutoResetEvent _event = new AutoResetEvent(false);

        /// <summary>
        /// Устанавливается в null, если управляемый объектом Scheduler ресурс не занят.
        /// </summary>
        private Thread _runningThread;

        /// <summary>
        /// Потоки и их запросы ожидающие выполнения
        /// </summary>
        private Dictionary<Thread, ISchedulerOrdering> _waiting = new Dictionary<Thread, ISchedulerOrdering>();

        /// <summary>
        /// Метод <see cref="Enter"/> вызывается перед тем, как поток начнет использовать управляемый ресурс.
        /// Метод не выполняется до тех пор пока управляемый ресурс не освободится и объект <see cref="Sheduler"/>
        /// не примет решение, что подошла очередь выполнения этого запроса
        /// </summary>
        /// <param name="s"></param>
        public void Enter(ISchedulerOrdering s)
        {
            var thisThread = Thread.CurrentThread;

            lock(this)
            {
                // Определяем не занят ли планировщик
                if(_runningThread == null)
                {
                    // Немедленно начинаем выполнение поступившего запроса
                    _runningThread = thisThread;
                    return;
                }
                _waiting.Add(thisThread, s);
            }
            
            lock(thisThread)
            {
                //Блокируем поток до тех пор, пока планировщик не решит сделать его текущим
                while(thisThread != _runningThread)
                {
                    _event.WaitOne();
                    _event.Set(); // даем возможность другим потокам проверить своё состояние
                    Thread.Sleep(1);
                }
                _event.Reset();
            }

            lock (this)
            {
                _waiting.Remove(thisThread);
            }
        }

        /// <summary>
        /// Вызов метода <see cref="Done"/> указывает на то, что текущий поток завершил работу
        /// и управляемый ресурс освободился
        /// </summary>
        public void Done()
        {
            lock (this)
            {
                if (_runningThread != Thread.CurrentThread)
                    throw new ThreadStateException(@"Wrong Thread");

                Int32 waitCount = _waiting.Count;
                if (waitCount <= 0)
                {
                    _runningThread = null;
                }
                else if (waitCount == 1)
                {
                    _runningThread = _waiting.First().Key;
                    _waiting.Remove(_runningThread);
                    _event.Set();
                }
                else
                {
                    var next = _waiting.First();
                    foreach (var wait in _waiting)
                    {
                        if(wait.Value.ScheduleBefore(next.Value))
                        {
                            next = wait;
                        }
                    }

                    _runningThread = next.Key;
                    _event.Set();
                }
            }
        }
    }

    /// <summary>
    /// Вспомогательный класс
    /// </summary>
    static partial class ConvertTo
    {
        /// <summary>
        /// Получить первый элемент коллекции
        /// </summary>
        /// <param name="collection"></param>
        /// <returns></returns>
        public static KeyValuePair<Thread, ISchedulerOrdering> First(this Dictionary<Thread, ISchedulerOrdering> collection)
        {
            foreach (var item in collection)
            {
                return item;
            }
            throw new ArgumentException();
        }
    }

}

using System;

namespace Digital_Patterns.Concurrency.Sheduler
{
    /// <summary>
    /// Если несколько операций ожидают доступа к ресурсу, класс<see cref="Scheduler"/> использует
    /// данный интерфейс для определения порядка выполнения операций.
    /// </summary>
    interface ISchedulerOrdering
    {
        Boolean ScheduleBefore(ISchedulerOrdering s);
    }
}

using System;
using System.Threading;

namespace Digital_Patterns.Concurrency.Sheduler
{
    /// <summary>
    /// Примерный код класса <see cref="JournalEntry"/>, который должен быть
    /// распечатан классом <see cref="Printer"/>
    /// </summary>
    class JournalEntry : ISchedulerOrdering
    {
        private static DateTime mTime = DateTime.Now;

        private DateTime _time;

        /// <summary>
        /// Возвращает время создания этого объекта
        /// </summary>
        public DateTime Time { get { return _time; } }

        private String _msg;

        public JournalEntry(String msg)
        {
            mTime = mTime.AddSeconds(1);
            _time = mTime;
            _msg = msg;
        }

        public void Do(Int32 id)
        {
            Console.WriteLine(String.Format(@"{0}: Start doing : {1} : {2}", id, _time, _msg));
            Thread.Sleep(1000);
            Console.WriteLine(String.Format(@"{0}: Finish do : {1} : {2}", id, _time, _msg));
        }

        /// <summary>
        /// Возвращает true, если данный запрос должен
        /// обрабатываться перед этим запросом.
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public Boolean ScheduleBefore(ISchedulerOrdering s)
        {
            if(s is JournalEntry)
            {
                var otherJournalEntry = (JournalEntry) s;
                return (this.Time < otherJournalEntry.Time);
            }
            return false;
        }
    }
}

using System;
using System.Threading;

namespace Digital_Patterns.Concurrency.Sheduler
{
    public class Example01
    {
        private Printer _printer;

        public void Run()
        {
            Console.WriteLine(@"Press any key for start, and press again for finish");
            Console.ReadKey();
            
            _printer = new Printer();
            new Thread(Thread1).Start();
            new Thread(Thread2).Start();
            new Thread(Thread3).Start();

            Console.ReadKey();
        }

        private void Thread1()
        {
            var msg1 = new JournalEntry(@"Buy toll 5.45 USD");
            var msg2 = new JournalEntry(@"Buy candy 1.05 USD");
            var msg3 = new JournalEntry(@"Buy chocolate 3.25 USD");
            _printer.Print(msg1);
            _printer.Print(msg2);
            _printer.Print(msg3);
        }

        private void Thread2()
        {
            var msg4 = new JournalEntry(@"Buy postcard 2.05 USD");
            var msg5 = new JournalEntry(@"Buy gerland 37.78 USD");
            _printer.Print(msg4);
            _printer.Print(msg5);
        }

        private void Thread3()
        {
            var msg6 = new JournalEntry(@"Buy ball 30.06 USD");
            var msg7 = new JournalEntry(@"Buy pipe 1.83 USD");
            _printer.Print(msg6);
            _printer.Print(msg7);
        }
    }
}

using System;
using Digital_Patterns.Concurrency.Sheduler;

namespace Digital_Patterns
{
    class Program
    {
        static void Main(string[] args)
        {
            new Example01().Run();

            Console.WriteLine(@"Press any key for end");
            Console.ReadKey();
        }
    }
}

Operációs rendszerek időzítőinek típusai

Operációs rendszerekben az időzítő egy rendszermodul, ami kiválasztja a következő feladatot a rendszer számára, és a következő futtatandó folyamatot. Az operációs rendszerek különböző típusú időzítőket támogathatnak, úgy mint hosszú távú, közép távú és rövid távú időzítőket. Az elnevezések arra a gyakoriságra utalnak, amivel hívják őket.

A folyamatidőzítő az operációs rendszernek az a része, ami dönt arról, hogy egy adott időpontban mely folyamat fusson. Rendszerint fel is függesztheti egy folyamat futását, hátrateheti a várakozási sorban, és egy másik folyamatot indíthat el. Az ilyen ütemezőket preemptívnek nevezik, szemben a kooperatív ütemezőkkel.

Hosszú távú ütemező

A hosszú távú ütemező arról dönt, hogy mely folyamatok és feladatok kerülhessenek futásra kész állapotba. Ha egy programot elindítanak, akkor először a hosszú távú ütemező foglalkozik vele, késlelteti vagy feljogosítja a futásra. Ez az ütemező határozza meg, hogy mely folyamatok futhatnak a gépen, és ez dönt arról, hogy mekkora legyen a párhuzamosság, és ez határozza meg a multiprogramozás fokát. További feladata az is, hogy a számításintenzív (inkább számoló) és az I/O-intenzív (inkább írással-olvasással foglalkozó) folyamatok száma körülbelül azonos legyen. Egy programban a kétféle folyamat elkülöníthető a termelő-fogyasztó programtervezési mintával.

Általában a kétféle folyamat csak párhuzamosan tud hatékonyan futni, különösen, ha a tervmintából származnak. Az azonos típusú folyamatok akadályozzák egymást. Például, ha I/O folyamatból van sok sok, akkor a futásra kész sor majdnem mindig üres lesz, és a rövid távú ütemezőnek nincs sok tennivalója, pedig jönnek a feladatok. Hasonlóan, ha számításintenzív folyamatokat választ, akkor az I/O ütemezőnek nem lesz sok tennivalója, a perifériák kihasználatlanul maradnak, és a rendszer megint kiegyensúlyozatlan marad. A jó rendszer kombinálja a kétféle típust. Modern operációs rendszerek ezt használják ki, hogy a valós idejű folyamatok elég CPU-időt kapjanak, hogy betarthassák a határidőket.

A hosszú távú időzítés különösen fontos nagy skálájú rendszereken, szuperszámítógépeken, klasztereken, batch feldolgozó rendszereken, és render farmokon. Például konkurens rendszereken gyakori elvárás az egymással kommunikáló folyamatok összeidőzítése, hogy a konkurens program gyorsabban futhasson, és ne kelljen a folyamatoknak várniuk egymásra. Ekkor speciális ütemezőket használnak az operációs rendszer ütemezőjének támogatására.

Közepes távú ütemező

A közepes távú ütemező ideiglenesen eltávolít folyamatokat a fő memóriából és másodlagos tárba helyezi, vagy megfordítva, amit gyakran úgy neveznek, hogy swap out vagy swap in, vagy inkorrektül kilapozás, belapozás. A közepes távú ütemező kilapozza azt a folyamatot, ami hosszabb ideje inaktív, alacsony prioritású, vagy gondjai támadtak a memóriahasználattal. További ok lehet a memóriafelszabadítás, ha a folyamat sok memóriát foglal. A folyamatot később visszahozza, ha van elég memória, vagy a blokk megszűnt, illetve nem várakozik magasabb prioritású folyamat. [Stallings, 396] [Stallings, 370]

Sok modern rendszeren a hosszú és a közepes távú ütemező össze van vonva. Az ütemező a futó binárisokat kilapozottnak tekinti. Kérésre belapozza a következő szakaszt, vagy lustán betölti.

Rövid távú ütemező

A rövid távú ütemező dönt arról, hogy mely futásra kész, memóriába töltött folyamatok közül melyik fusson. Így a rövid távú ütemezőnek sokkal gyakrabban kell döntenie, mint a hosszú vagy közepes távúnak; minden időszeletben döntést kell hoznia. Lehet preemptív vagy kooperatív. A preemptív ütemező programozható megszakításkezelőt hív, ami kernel módban fut, és megvalósítja az ütemezőfüggvényt.

Diszpécser

A diszpécser az ütemező rendszer eleme. Ez a modul hajtja végre a rövid távú ütemező döntéseit, utalja ki a processzoridőt. A kontrollt kernel módban végzi, ebbe rendszerhívás vagy megszakítás esetén kapcsol. A diszpécser által végzett feladatok a következők:

• Kontextusváltás esetén elmenti, hogy melyik program hol tartott, és elmenti az állapotát; ezeket közösen kontextusnak is hívják. Ezután betölti az új program kontextusát.
• Felhasználói módba vált.
• A felhasználói programban a megfelelő helyre ugrik, és a megfelelő állapottal újraindítja.

A diszpécsernek olyan gyorsnak kell lennie, amennyire lehetséges, mivel minden kontextusváltáskor meghívódik. A kontextusváltás alatt a processzor kihasználatlan, ezért a fölösleges kontextusváltásokat el kell kerülni.

Implementációk

Az algoritmus lehet olyan egyszerű, mint a round robin, ahol az ütemező ciklikusan kapcsolgat a folyamatok között, és mindegyik ugyanakkora időszeletet kap. Azaz, ha három folyamat van, A, B és C, akkor az A folyamat kap egy időszeletet, majd a B és a C jön, aztán újra az A, és így tovább.

Bonyolultabb algoritmusok használhatnak prioritást, vagy fontosságot. A rendszerfolyamatok például mindig fontosabbak a felhasználói folyamatoknál. SMP rendszerekben a processzoraffinitás a teljes rendszer teljesítményét növeli, még ha le is lassítja az adott folyamatot. Ez a cache trashing csökkentésével járul hozzá a rendszer felgyorsításához.

Operációk rendszerek ütemezőinek rövid jellemzése

A különböző operációs rendszerek ütemezésére a következők jellemzők:

Operációs rendszer	Preemptív-e	Algoritmus
Amiga OS	Igen	Priorizált round-robin ütemező
FreeBSD	Igen	Többszintű visszacsatolásos sor
Linux kernel a 2.6.0 előtt	Igen	Többszintű visszacsatolásos sor
Linux kernel 2.6.0–2.6.23	Igen	O(1) ütemező
Linux kernel 2.6.23-tól	Igen	Teljesen fair ütemező
klasszikus Mac OS 9 előtt	Nem	Kooperatív ütemező
Mac OS 9	Részben	Csak MP taszkokra preemptív, szálakra és folyamatokra nem
macOS	Igen	Többszintű visszacsatolásos sor
NetBSD	Igen	Többszintű visszacsatolásos sor
Solaris	Igen	Többszintű visszacsatolásos sor
Windows 3.1x	Nem	Kooperatív ütemező
Windows 95, 98, Me	Részben	Csak 32 bites folyamatokra preemptív, és kooperatív a 16 biteseknek
Windows NT (továbbá 2000, XP, Vista, 7 és Server)	Igen	Többszintű visszacsatolásos sor

IBM OS/360 és utódai

Az IBM OS/360 három különböző ütemezővel volt elérhető, amelyek között akkorák voltak a különbségek, hogy gyakran különböző operációs rendszernek tekintették őket:

• Az egyszerű szekvenciális ütemező, ismert úgy is, mint elsődleges vezérlőprogram (PCP) szekvenciális sort használt.
• A többszörös szekvenciális ütemező ismert, mint multiprogramozás rögzített számú feladattal (MFT) támogatta több feladat konkurens végrehajtását. A prioritás vagy alapértelmezett volt, vagy be kellett állítani minden feladatra. Az MFT II verzió hozzáadta az alfeladatok támogatását is. Minden folyamatnak memóriát kellett igényelnie, amit a feladatok végrehajtásához használhat.
• A többszörös prioritású ütemező (MVT) már a kezdetektől támogatta az alfeladatokat; végrehajtása előtt minden feladatnak prioritást és memóriát kellett igényelnie.

Az MVS virtuális tár verziói ehhez hozzáadták a workload intézőt, ami a számítógép erőforrásait ütemezi a telepítés alatt megadott részletes beállítások alapján.

Windows

A korai MS-DOS és Windows rendszerek egyfeladatosak voltak, így nem volt szükségük ütemezőre. A Windows 3.1x kooperatív ütemezőt használt, ami nem szakíthatta meg a programok futását. Arra hagyatkozott, hogy a program mondja meg azt, hogy mikor végzett, és adja vissza az erőforrásokat ahhoz, hogy a következő program futhasson. A Windows 95 ütemezője részben preemptív volt, a 16 bites alkalmazások kompatibilitási okokból kooperatívan futottak.

A Windows NT alapú rendszerek többszintű visszacsatolásos sort használnak. A definiált szintek száma 32, 0-tól 31-ig. A normál prioritások 0-tól 15-ig terjednek, a 16-31 valós idejű prioritások, amelyek igényléséhez privilégiumok kellenek. A 0 az operációs rendszernek van fenntartva. A felhasználók öt szintet tudnak megadni az intézőben vagy API-kban ezek közül a prioritások közül. A kernel megváltoztathatja a szál prioritását aszerint, hogy mennyit használja az I/O-t és a processzort, vagy hogy mennyire interaktív. Az I/O intenzív és az interaktív folyamatok prioritását megnöveli, míg a főként számításokat végzőkét csökkenti (ami rossz hír a termelő-fogyasztó tervminta számára). A Windows Vistában módosították az ütemezőt, hogy kihasználja a processzor ciklusszámláló regiszterét. Így az ütemező megtudta, hogy egy szál hány ciklusnál tart, szemben az addig használt intervallum-ütemező megszakítással. A Vista prioritásos ütemezőt használ az I/O sorra, így a töredezettség-mentesítő és más hasonló programok nem zavarják az előtérben futó műveleteket.

Klasszikus Mac OS és macOS

A Mac OS 9 kooperatív ütemezőt használ a szálakra, ahol egy folyamat kezel több összetartozó szálat, de preemptívet a multiprocesszáló feladatokra. A folyamatintéző folyamat egy speciális multiprocesszáló feladattal fut együtt, ez a kék feladat. Ezeket round-robin ütemezővel kooperatívan ütemezi; a következő szál akkor indul, ha az előző explicit blokkolta magát, például WaitNextEvent hívásával. Minden folyamatnak saját másolata van a szálkezelőből, ami kooperatívan ütemezi a folyamat szálát; egy szál visszaadja a vezérlést az ütemezőnek YieldToAnyThread vagy YieldToThread hívásával.

A macOS többszintű visszacsatolásos sort használ, ahol négy különböző prioritás adható meg: normál, magas prioritású rendszer, csak kernel mód, és valós idejű. A szálak ütemezése preemptív; a macOS a kooperatív ütemezést is támogatja a Carbon API-val megvalósított szálkezelőjével.

AIX

Az AIX 4 verzió három különböző ütemezőt nyújt:

• FIFO: Ha egy szálat ez ütemez be, akkor végzésig futhat, vagy visszaadhatja az erőforrásokat az ütemezőnek blokkolódással vagy explicit módon. Az ütemező elveszi a vezérlést, ha egy magasabb prioritású folyamat jön.
• Round robin: priorizált round robin, 10ms-es időszeletekkel. A vezérlés visszavételével a folyamat a prioritásának megfelelő sor végére kerül.
• OTHER: a folyamat prioritásáa nincs előre megadva, hanem menet közben számolja az ütemező. Egy folyamat elvesztheti a vezuérlést, mert prioritása lecsökkent, így van magasabb prioritású folyamat. Ez az alapértelmezett AIX 3 ütemező viselkedése.

Az AIX 5 öt különböző ütemezőt nyújt, ahol a FIFO-nak három különböző implementációja van, FIFO, FIFO2, FIFO3. A round robin elnevezése AIX-ben SCHED_RR, és a fair round robiné SCHED_OTHER.

Linux

A Linux 2.4 rendszermag O(n) ütemezőt használt több szintű visszacsatolásos sorral. A prioritások 0-tól 140-ig terjedtek; 0-99 a valós idejű feladatoké és a 100-140 a többieké. Valós idejű feladatokra az időszelet 200 ms, a többire 10 ms volt. Az ütemező algoritmus a prioritásos round robin volt, ahol a magasabb prioritású feladatokból indított el egyet, ami az időszelet végéig futott. Ezután a futott feladatok sorába, amit majd az ütemező felcserél a várakozó sorral.

Néhány kereskedelmi Linux rendszer, például az SUSE Linux Enterprise Server az Alan Cox által visszaportolt O(1) ütemezővel helyettesítette ezt az ütemezőt.

A Linux 2.6.0-tól kezdve a 2.6.22-ig a Linux rendszermag O(1) ütemezőt használt, amit Molnár Ingó és társai fejlesztettek ki a 2.5 alá. Con Kolivas foltokat készített, amelyekkel javította az ütemező interaktivitását.

Con Kolivas ütemezője, a Rotating Staircase Deadline (forgó lépcsőház határidő) inspirálta Molnár Ingót a teljesen fair ütemező (CFS) kifejlesztésére, amivel helyettesítette a korábbi O(1) ütemezőjét. Bejelerntésében meg is említette Kolivast. Ez az első fair sort használó folyamatütemező, amit elterjedten használnak operációs rendszerben.

A CFS egy jól tanulmányozott, klasszikus ütemező algoritmust használ, a fair sort, amit eredetileg csomagokhoz találtak fel. Korábban stride (nagy lépés) ütemezőnek nevezték. A CFS ütemező bonyolultsága O(log N), ahol N a feladatok száma a futási sorban. A feladat kiválasztása konstans idejű, de futás után visszatenni O(log N), mivel a futási sor piros-fekete faként van implementálva.

A CFS alternatívája a szintén Con Kolivas által készített BFS (Brain Fuck Scheduler).

FreeBSD

A FreeBSD többszintű visszacsatolásos sort használ, ahol a prioritásokat a 0–255 tartományból osztja. 0–63 a megszakításoké, 64–127 a kernel felső szintjéé, 128–159 a valós idejű felhasználói szálaké, 160–223 az időosztásos felhasználói szálaké, és 224–255 az idle (pihenő) felhasználói szálaké. A Linuxhoz hasonlóan aktív sort használ, de használ idle sort is.

NetBSD

A NetBSD többszintű visszacsatolásos sorában a prioritások 0–tól 223-ig terjednek. 0–63 időosztásos szálaknak (alapértelmezett, SCHED_OTHER), a 64–95 a kerneltérbe lépett felhasználói szálaké, 96-128 a kernel szálaké, 128–191 a felhasználói valós idejű szálaké (SCHED_FIFO és SCHED_RR), és 192–223 a megszakításoké.

Solaris

A Solaris szintén többszintű visszacsatolásos sorban tartja számon a szálakat, illetve feladatokat. A prioritások 0-tól 169-ig terjednek. 0–59 az időosztásos szálaké, 60–99 a rendszer szálaké, 100–159 a valós idejű szálaké, és 160–169 az alacsony prioritású megszakításoké. A Linuxszal szemben, ha egy szál felhasználta az időszeletét, akkor új prioritást kap, és újra bekerül a sorba. A Solaris 9 ütemezője bevezette a rögzített prioritású és a fair ütemezésű osztályokat. A rögzített prioritású szálak prioritása nem változhat, míg a többié igen. A fair ütemezésű szálak a CPU megosztásait használják a szálak priorizálására az ütemezési döntések meghozásához. Ezek jelzik, hogy milyen és mennyi erőforrást igényelnek az egyes szálak. Folyamatok egy halmazának adják ki, amelyeket együtt projektnek neveznek.

Kapcsolódó szócikkek

• Közvetítő programtervezési minta

Fordítás

Ez a szócikk részben vagy egészben a Scheduler pattern című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Források

• Mark Grand. Patterns in Java Volume 1: A Catalog of Reusable Design Patterns Illustrated with UML. — Wiley & Sons, 1998. — 480 с. — ISBN 0471258393.